UVA12177 First Knight

dp(i,j)dp(i,j) 表示由 (i,j)(i,j) 走到 (n,m)(n,m) 的期望步数。

那么显然有转移:

dp(i,j)=1+(up(i,j)×dp(i+1,j)+down(i,j)×dp(i1,j)+left(i,j)×dp(i,j1)+right(i,j)×dp(i,j+1))dp(i,j)=1+(up(i,j) \times dp(i+1,j) + down(i,j) \times dp(i-1,j) + left(i,j) \times dp(i,j-1) + right(i,j) \times dp(i,j+1))

其中 up,down,left,rightup,down,left,right 分别表示 (i,j)(i,j) 向上/下/左/右走的概率。

边界条件: dp(n,m)=0dp(n,m)=0

然后你发现它们互相有依赖,不能直接转移,所以直接高斯消元。

但这样时间复杂度是 O(n3m3)\mathcal O(n^3m^3),考虑优化

  1. 因为每一个方程不为 00 的系数最多 55 个,所以增广矩阵其实很稀疏,系数为 00 就不需要加减消元了。
  2. 我们只需要 dp(1,1)dp(1,1) ,所以消成下三角矩阵就可以了。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define eps 1e-16

const int MAXN = 50;
int n , m , fn;
double a[ MAXN * MAXN + 5 ][ MAXN * MAXN + 5 ];

void Gauss( ) {
    for( int i = fn ; i >= 1 ; i -- ) {
        for( int j = i - 1 ; j >= 1 ; j -- ) {
            double t = a[ j ][ i ] / a[ i ][ i ];
            if( fabs( t ) < eps ) continue;
            for( int k = i ; k >= 1 ; k -- )
                a[ j ][ k ] -= t * a[ i ][ k ];
            a[ j ][ fn + 1 ] -= t * a[ i ][ fn + 1 ];
        }
    }
}

pair< int , int > dir[ 4 ] = { { 1 , 0 } , { 0 , 1 } , { -1 , 0 } , { 0 , -1 } };
double p[ MAXN + 5 ][ MAXN + 5 ][ 4 ];

int Hash( int x , int y ) {
    if( x < 1 || x > n || y < 1 || y > m ) return fn + 2; //越界
    return ( x - 1 ) * m + y;
}
int main( ) {
    while( scanf("%d %d",&n,&m) && ( n + m ) ) {
        fn = n * m;
        for( int k = 0 ; k < 4 ; k ++ )
            for( int i = 1 ; i <= n ; i ++ )
                for( int j = 1 ; j <= m ; j ++ )
                    scanf("%lf",&p[ i ][ j ][ k ]);
        memset( a , 0 , sizeof( a ) );
        for( int i = 1 ; i <= n ; i ++ )
            for( int j = 1 ; j <= m ; j ++ ) {
                int h = Hash( i , j );
                a[ h ][ h ] = -1;
                if( i == n && j == m ) continue;
                a[ h ][ fn + 1 ] = -1;
                for( int k = 0 ; k < 4 ; k ++ )
                    a[ h ][ Hash( i + dir[ k ].first , j + dir[ k ].second ) ] = p[ i ][ j ][ k ];
            }
        Gauss( );
        printf("%.1f\n", a[ 1 ][ fn + 1 ] / a[ 1 ][ 1 ] );
    }
    return 0;
}